/**
 * @file     coin.h
 * @author   Han Yaoting
 * @date     Sun Dec 24 2023
 * 
 * @brief    Homework4 of D.S.A. Functions of project to find out the minimum number of coins that make the total amount of n cents
 * 
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;  
  
/**  
 * @brief  A struct that contains the face value and quantity of the coin.  
 */  
struct COIN {  
    int Value;          
    int Count;          /**< The number of coins currently available */
};  

/**  
 * @brief  Judge and find the minimum number of coins that make up the amount of the coin sought. 
 * 
 * @return Minimum number of coins
 */  
int Min_coins (int Charges, vector<COIN>& coins) {
    vector<int> dp(Charges + 1, INT_MAX);                       /**<Create an intermediate array*/      
    dp[0] = 0;          

    
        for (int i = 1; i <= Charges; i++) {
            for (COIN coin : coins){
                for (int j = 0; j < coin.Count; j++) {          /**< Go through each coin */
                if (coin.Value <= i) {
                    int Sub_res = dp[i - coin.Value];           /**< Recursive */
                    if (Sub_res != INT_MAX && Sub_res + 1 < dp[i] && coin.Count > 0) { /**< If there is a minimum number of coins for the remaining amount, and the number of coins after using the current coins is smaller, and the current number of coins is greater than 0 */
                        dp[i] = Sub_res + 1;                    /**< Update the intermediate array  */            
                        coin.Count--;
                    }
                }
            }
        }
    }

    return dp[Charges] == INT_MAX ? -1 : dp[Charges];           /**< Returns the minimum number of coins, and -1 if there is no solution */
}

